本来是一个很正常的贪心,然后神Sooke提出了一个结论,我整理后如下:
设是这个题输出的数组中,满足的一段前缀的长度,那么
不太严谨的口胡证明
首先可以直接验证得到,对于:
分析那个标程,可以发现就是注释标出的那行执行到的次数
如果某一时刻数组的区间中最小值在的位置,那么这就是一个好的状态
对于一个好的状态,如果是奇数,轮就能回到好的状态,并且这个过程中执行了一次注释标出的那行,于是
如果是偶数,轮才能回到好的状态,这个过程中没有执行到注释标出的那行
结合的边界条件就可以推出来了
リンちゃんなう!
本来是一个很正常的贪心,然后神Sooke提出了一个结论,我整理后如下:
设f(n)是这个题输出的数组中,满足a[i]=i的一段前缀的长度,那么
f(2)=2
f(2n)=1,n>1
f(n)=2n的最大奇因子−1,otherwise
不太严谨的口胡证明
首先n≤4可以直接验证得到,对于n>4:
分析那个标程,可以发现f(n)就是注释标出的那行执行到的次数
如果某一时刻b数组的[l,r)区间中最小值在b[l]的位置,那么这就是一个好的状态
对于一个好的状态,如果r−l是奇数,2轮就能回到好的状态,并且这个过程中执行了一次注释标出的那行,于是
f(n)=f(n−2)+1,n是奇数
如果r−l是偶数,2r−l轮才能回到好的状态,这个过程中没有执行到注释标出的那行
f(n)=f(2n),n是偶数
结合n≤4的边界条件就可以推出来了